Today's processors are more powerful and faster than ever. As a result, even memory access times, typically measured in tens of nanoseconds, can be an impediment to a processor's running at full speed. Generally, the CPU time of a processor is the sum of the clock cycles used for executing instructions and the clock cycles used for memory access. While modern processors have improved greatly in terms of instruction execution time, the access times of reasonably-priced memory devices have not similarly improved.
A common method of compensating for memory access latency is memory caching. Memory caching takes advantage of the inverse relationship between the capacity and the speed of a memory device; that is, a larger (in terms of storage capacity) memory device is generally slower than a smaller memory device. Additionally, slower memories are less expensive, and are therefore more suitable for use as a portion of mass storage, than are more expensive, smaller, and faster memories.
In a caching system, memory is arranged in a hierarchical order of different speeds, sizes, and costs. For example, a small, fast memory, usually referred to as a “cache memory”, is typically placed between a processor and a larger, but slower, main memory. The cache memory has the capacity to store only a small subset of the data stored in the main memory. The processor needs only a certain, small amount of the data from the main memory to execute individual instructions for a particular application. The subset of memory is chosen based on an immediate relevance based on well-known temporal and spacial locality theories. This is analogous to borrowing only a few books at a time from a large collection of books in a library to carry out a large research project. Just as research may be as effective and even more efficient if only a few books at a time are borrowed, processing of a program is efficient if a small portion of the entire data stored in main memory is selected and stored in the cache memory at any given time.
An input/output (“I/O”) cache memory located between main memory and an I/O controller (“IOC”) will likely have different requirements than a processor cache memory, as it will typically be required to store more status information for each line of data, or “cache line”, than a processor cache memory. In particular, an I/O cache will need to keep track of the identity of the particular one of a variety of I/O devices requesting access to and/or having ownership of a cache line. The identity of the current requester/owner of the cache line may be used, for example, to provide fair access. Moreover, an I/O device may write to only a small portion of a cache line. Thus, an I/O cache memory may be required to store status bits indicative of which part of the cache line has been written or fetched. Additionally, one or more bits will be used to indicate line state of the corresponding cache line; e.g., private, current, allocated, clean, dirty, being fetched, etc. Still further, in an I/O cache, there is no temporal locality; that is, the data is used just once. As a result, an I/O cache does not need to be extremely large and functions more like a buffer to hold data as it is transferred from main memory to the I/O device and vice versa.
As I/O cards become faster and more complex, they can issue a greater number of direct memory access (“DMA”) requests and have more DMA requests pending at one time. The IOC, which receives these DMA requests from I/O cards and breaks up each into one or more cache line-sized requests to main memory, generally has a cache to hold the data that is fetched from main memory in response to each DMA request, but the amount of data that can be stored in the cache is fixed in size and is a scarce resource on the IOC chip. When the IOC attempts to access a memory location in response to a DMA request from an I/O card, it first searches its cache to determine whether it already has a copy of the requested data stored therein. If not, the IOC attempts to obtain a copy of the data from main memory.
As previously indicated, when an IOC fetches data from main memory in response to a DMA request from an I/O card, it needs to put that data into its cache when the data is delivered from memory. If the cache is full (i.e., if there are no empty cache lines available), the new data may displace data stored in the cache that has not yet been used. This results in a performance loss, as the data that is displaced must subsequently be refetched from main memory.
I/O transfers tend to be long bursts of data that are linear and sequential in fashion. Prefetch data techniques allow I/O subsystems to request data stored in memory prior to an I/O device's need for the data. By prefetching data ahead of data consumption by the device, data can be continuously sent to the device without interruption, thereby enhancing I/O system performance. The amount of data that is prefetched in this manner for a single DMA transaction is referred to as “prefetch depth.” The “deeper” the prefetch, the more data that is fetched before the data from the first request has been consumed.
However, some DMA requests, in particular, Peripheral Component Interconnect (“PCI”) DMA reads, are speculative by nature. This is due to the fact that only the beginning address, but not the length, of the data is specified in a PCI DMA read request. Hence, a PCI DMA read will use prefetch operations to fetch data that the IOC “guesstimates” that the I/O device will require before that data is actually requested by the device. In contrast, PCIX standard DMA reads specify both a starting address and a length of the data to be read and are therefore nonspeculative. In one prior art embodiment, a prefetch machine is used to predict future requests based on a current request and keeps track of memory requests that have already been initiated and queued.
In a worst case scenario, the IOC could issue prefetch requests to main memory for every cache line of every pending DMA transaction from every IO card. In this worst case scenario, the capacity of a typical IOC cache would be insufficient to accommodate all of the requested cache lines. Alternatively, the cache could be enlarged, resulting in a IOC cache that is much bigger than it needs to be under normal circumstances.
In cases in which the number of requests issued is greater than the size of the cache, there will be contention for cache lines. In one prior art embodiment, a cache replacement algorithm (“CRA”) is implemented by the IOC to select which cache line(s) to displace, or “flush”. It will be recognized that CRAs that are random may displace cache lines that have not yet been used. Other CRAs flush old or unused cache lines first, as there is a greater likelihood that those lines will not be needed; however, such algorithms give no weight to whether a cache line contains speculative, as opposed to nonspeculative, data when considering whether to flush a particular line.